package puzzle_a_estrela;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * O nó da árvore de busca
 */
public class No {

    private final Estado estado;
    private final No pai;
    private final Acao acao;
    private final double custo;
    private final int profundidade;
    private int valorHeuristica;

    protected No() {
        this(null, null, null, 0);
    }

    /**
     * Cria o nó de busca sem pai
     */
    public No(Estado estado) {
        this(estado, null, null, 0);
    }

    /**
     * Inicialização do nó de busca
     */
    public No(Estado estado, No pai, Acao acao, double custo) {
        this.estado = estado;
        this.pai = pai;
        this.acao = acao;
        this.custo = custo;
        if (pai != null) {
            this.profundidade = pai.getProfundidade() + 1;
        } else {
            this.profundidade = 0;
        }
        this.valorHeuristica = -1;
    }

    /**
     * Expande o nó atual.
     */
    public No[] expandir() {
        AcaoEstado[] sucessores = estado.sucessores();
        No[] descendentes = new No[sucessores.length];
        for (int a = 0; a < sucessores.length; a++) {
            Acao acao = sucessores[a].getAcao();
            Estado filho = sucessores[a].getEstado();
            descendentes[a] = new No(filho, this, acao, this.getCusto() + estado.custoCaminho(acao));
        }
        return descendentes;
    }

    /**
     * Determina todas as ações que foram feitas para se chegar nesse estado
     */
    public Acao[] getAcoes() {
        Acao[] steps = new Acao[profundidade];
        No node = this;
        for (int i = 0; i < profundidade; i++) {
            steps[i] = node.getAcao();
            node = node.getPai();
        }
        return steps;
    }

    /**
     * Retorna a última ação que nos trouxe a esse estado
     */
    public Acao getAcao() {
        return acao;
    }

    /**
     * Custo acumulado
     */
    public double getCusto() {
        return custo;
    }

    /**
     * Profundidade da árvore
     */
    public int getProfundidade() {
        return profundidade;
    }

    /**
     * Retorna o pai desse nó
     */
    public No getPai() {
        return pai;
    }

    /**
     * Retorna o estado desse nó
     */
    public Estado getEstado() {
        return estado;
    }

    /**
     * Armazena o valor da heurística para o nó
     */
    public void setValorHeuristica(int valor) {
        this.valorHeuristica = valor;
    }

    /**
     * Retorna o valor da heuristica para o nó
     */
    public int getValorHeuristica() {
        return valorHeuristica;
    }

    /**
     * Insere o nó na lista ordenada por distância
     */
    private static ArrayList<No> addToFilaPrioridades(No no, ArrayList<No> lista, Heuristica h, int custoAdicional) {

        // Calcula o custo do nó
        int custoNo = no.getValorHeuristica() + custoAdicional;

        // Insere o nó na posição correta
        for (int x = 0; x <= lista.size(); x++) {

            // Se não encontrou o nó na lista, o adiciona nela
            if (x == lista.size()) {
                lista.add(no);
                break;
            }

            // Adiciona o nó com a politica FIFO se ele tem o mesmo custo do nó encontrado
            if (custoNo < lista.get(0).getValorHeuristica()) {
                lista.add(x, no);
                break;
            }
        }

        return lista;
    }

    public static No buscaGulosa(NPuzzleEstado initial, Heuristica hx) {
        No head;
        ArrayList<No> filaPrioridades = new ArrayList<No>();

        filaPrioridades.add(new No(initial));
        while (!filaPrioridades.isEmpty()) {
            head = filaPrioridades.remove(0);
            if (estadoRepetido(head)) {
                continue;
            }

            // Goal state
            if (head.getEstado().estadoFinal()) {
                return head;
            }

            for (No move : Arrays.asList(head.expandir())) {
                if (move.getValorHeuristica() == -1) {
                    move.setValorHeuristica(hx.getDistancia(move));
                }
                filaPrioridades = addToFilaPrioridades(move, filaPrioridades, hx, 0);
            }
        }

        // Didn't find a solution
        return null;
    }

    /*
     * Busca A*
     */
    public static No buscaAEstrela(NPuzzleEstado inicial, Heuristica h) {
        //Inicializa as variaveis noCorrente, filadeprioridades
        No noCorrente = new No(inicial);
        ArrayList<No> filaPrioridades = new ArrayList<No>();
        int custo;

        //Adiciona o no inicial a fila de prioridades
        filaPrioridades.add(new No(inicial));
        while (!filaPrioridades.isEmpty()) {

            //Se fila de prioridades não vazia ele pega o no inicial para corrente e retira da fila
            noCorrente = filaPrioridades.remove(0);

            //Verifica se o no é um estado repetido
            if (estadoRepetido(noCorrente)) {
                continue;
            }

            // Verifica se chegou ao estado final
            if (noCorrente.getEstado().estadoFinal()) {
                return noCorrente;
            }

            custo = (int) noCorrente.getCusto();
            for (No no : Arrays.asList(noCorrente.expandir())) {
                if (no.getValorHeuristica() == -1) {
                    no.setValorHeuristica(h.getDistancia(no));
                }
                filaPrioridades = addToFilaPrioridades(no, filaPrioridades, h, custo);
            }
        }

        // Não encontrou solução!! Isso nunca acontece na busca A*
        return null;
    }

    /**
     * Verica estado repetido
     */
    private static boolean estadoRepetido(No no) {
        ArrayList<No> visitados = new ArrayList<No>();
        Estado estado1, estado2;
        No head = no;

        // Adiciona a lista de nó de visitados com o próprio nó e mais 5 ancestrais dele
        visitados.add(head);
        for (int i = 0; i < 5; i++) {
            if (head.getPai() != null) {
                visitados.add(head.getPai());
                head = head.getPai();
            }
        }

        // Compara todos os elementos da lista, uns com os outros
        for (int i = 0; i < visitados.size(); i++) {
            for (int j = 0; j < visitados.size(); j++) {
                if (i != j) {
                    estado1 = (NPuzzleEstado) visitados.get(i).getEstado();
                    estado2 = (NPuzzleEstado) visitados.get(j).getEstado();
                    if (estado1.equals(estado2)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

}
